As microprocessor systems become more and more complex, new techniques are required to ensure the efficient use of system resources. For example, in many multi-processor systems, there are several microprocessors trying to share some of the same system resources, such as memory storage, a printer, or a port to a display screen. It is crucial in such multi-processor systems that the communication pathways or buses carrying information between the microprocessors and the system resources are used in the most efficient way possible.
Messages traveling from microprocessors to system resources across communication pathways are analogous to cars traveling from one part of town to another across roads. If the traffic on the communication pathway is not handled as efficiently as possible, the traffic will start to back up and congest the pathways. As a result, communications between microprocessors and system resources will slow down. This will cause the whole system to operate more slowly. If the congestion on the communication pathways is bad enough, like rush hour traffic, the whole microprocessor system can be brought to a slow creep.
Unlike cars, however, only one message at a time can be transferred across a microprocessor bus using conventional electrical conductors. Thus, only one microprocessor at a time can be in control of the bus and can send information to another microprocessor or system resource.
Microprocessors must arbitrate among themselves to determine which processor will win the arbitration and be in control of the bus. Only when a microprocessor has won arbitration and is thus the "bus master" can that microprocessor then send or receive information across the bus. Other microprocessors must wait their turn to become the bus master in order to send or receive information across the bus.
Aside from the need to efficiently utilize buses, the need also exists to efficiently share system resources, such as, for example, a printer. If multiple processors are sharing a printer, there must be a way to indicate which processor is currently using the resource and whether that processor is performing a function that must not be disturbed. Semaphores are used for this function in many multi-processor systems.
Semaphores are a type of flag or status indicator that reflects the present status of a system resource. Usually the status information in a semaphore indicates whether or not the system resource is presently being used. In some multi-processor systems, the semaphore may also include information about which microprocessor is using the resource, and possibly even the type of function being performed on the resource.
For example, a particular location in memory can be designated as the location of the semaphore for a printer resource. If any microprocessor wants to use the printer, that microprocessor must read the printer semaphore by reading that particular location in memory. The printer semaphore contains information on the status of the printer, such as whether the printer is currently being used. If the printer semaphore indicates that the printer is currently being used and is thus busy, the microprocessor must wait. The microprocessor can continue to poll the printer semaphore by periodically reading the printer semaphore to see if the printer is still being used or if it has become available.
Once the printer semaphore indicates that the printer is available, the waiting microprocessor writes to the printer semaphore to change its status to busy. The waiting microprocessor has thus effectively locked the printer resource for its own use. No other processors can use the printer while the printer's semaphore indicates that the printer is being used. Once the waiting processor has finished using the printer, it writes a new value to the printer semaphore location in order to change the printer semaphore to indicate that the printer is once again available.
There is a significant problem that arises in systems that use semaphores to allocate shared system resources. The problem arises when more than one microprocessor is polling the semaphore of a shared resource to see if the resource has become available yet. For example, assume microprocessor #1 and microprocessor #2 are both polling the printer semaphore. Microprocessor #1 is the first to read the printer semaphore after it has been changed to indicate that the printer is available. Microprocessor #2 now reads the printer semaphore and also learns that the printer is available. Neither microprocessor #1 nor microprocessor #2 is aware that another processor is competing for the use of the printer.
If microprocessor #1 receives an interrupt, microprocessor #1 must execute a software interrupt routine before resuming where it left off. Meanwhile, microprocessor #2 writes a value to the printer semaphore to indicate that the printer is now busy. Microprocessor #2 then proceeds to use the printer. Microprocessor #1 finishes its interrupt routine and resumes where it left off in its software program. Microprocessor #1 left off knowing that the printer was available. Microprocessor #1 thus writes a value to the printer semaphore to indicate that the printer is now busy and then proceeds to try to use the printer. But the printer is already being used by Microprocessor #2. Thus a collision results on the bus going to the printer. As a result, the printer is not able to correctly print out the information from either of the microprocessors.
One way to solve this problem is to lock the bus during the entire time it takes for a processor to perform both a read and a subsequent write to a semaphore in memory. "Locking" the bus means that the present bus master is the only processor that is allowed to use the bus for multiple bus cycles. Normally, arbitration for the bus occurs frequently so that all processors have a chance to use the bus at regular intervals. Locking the bus is performed so that no other processor has a chance to become the bus master and use the bus.
A processor that has won the bus arbitration and has become the bus master locks the bus before reading a semaphore. Because the bus is locked, no other processors can use the bus. The bus master processor then reads the semaphore from memory and determines if the system resource is available. If the resource is busy, the bus master processor releases the bus lock, and arbitration for a new bus master can take place. But if the resource is available, the bus master processor continues to keep the bus locked until the bus master processor is able to write a new value to the semaphore indicating that the system resource is now busy.
By locking the bus, only one processor at a time is able to read a semaphore, see that the system resource is available, and write back a value to the semaphore to indicate that the resource is now busy. Thus, locking the bus guarantees that only one processor at a time will actually use a system resource. Collisions on the bus are therefore avoided.
However, locking the bus has a very significant drawback. It may cause communications between other microprocessors and system resources to slow down considerably. And as a result, the whole system may operate much more slowly.
As an example, a problem may arise when a hierarchical bus structure utilizing multiple busses is used. If the bus master processor and the memory containing the semaphore are on buses that are very distant from one another, the bus master must continuously lock all of the buses between itself and the distant memory during both the read and the subsequent write to the semaphore. This is not a very effective use of the bus time, especially considering that an access to a semaphore is usually a very common access in a multi-processor system. Thus, locking the bus is not a very satisfactory solution.